Kahn's algorithm is straightforward to implement using a queue and tracking the in-degree of every node.

  • We use a deque (double-ended queue) to act as our simple FIFO queue for nodes ready to be processed.
  • 1. Compute In-Degrees: We loop through the graph once to build the in_degree dictionary for all nodes.
  • 2. Initialize Queue: We add all nodes with an in-degree of 0 to our queue, as they have no dependencies.
  • 3. Main Loop: The process continues as long as the queue is not empty, ensuring all reachable nodes are processed.
  • 4. Pop and Process: We dequeue the next available node and add it to the sorted list (the result).
  • 5. "Remove" Edges: We decrement the in-degree of all neighbors, simulating the removal of the processed node's outgoing edges.
  • 5b. Add New Nodes: If a neighbor's in-degree drops to zero, it means all its dependencies are met, so it is added to the queue.
  • 6. Cycle Check: If the final sorted list does not contain all nodes, the graph must contain a cycle and is not a DAG.